//
//  Train. 完全背包问题.swift
//  LeetCodeTrain
//
//  Created by mojiit on 2021/6/15.
//  Copyright © 2021 rjb. All rights reserved.
//

import Foundation
// 完全背包问题
// 一个物品可以被使用很多次
// 定义dp[i]容量为i时的最大
class SolutionAllBagTrain {
    func bagMaxValue(capacity:Int, weight:[Int], value:[Int]) ->Int {
        var dp = Array(repeating: 0, count: capacity + 1)
        // 0 - 1 背包问题：当物品数量一定时，容量变大时，也只能判定一次自己是选还是不选
        // 0 - 1 背包利用的没有当前物品的历史数据
        // 完全背包问题：当物品数量是一定时，容量变大时，会不断的判定当前的物品是选还是不选。
        // 完全背包问题利用的是可能已经选了当前物品的数据；
        // 0-1背包问题与完全背包问题区别，当前物品只使用一次，当前物品可以使用多次。
        // 在代码上的区别就是利用的历史数据不一样。
        // 0-1背包利用的是上一行的数据
        // 完全背包利用的是本行的数据
        for i in 0..<weight.count {
            for j in 0...capacity {
                let v = value[i]
                let w = weight[i]
                if j < w {
                    continue
                }
                dp[j] = max(dp[j - w] + v, dp[j])
            }
        }
        return dp[capacity]
    }
    
    
    
    static func test (){
        let weight = [1,3,4]
        let value = [15, 20, 30]
        let size = 4
        let solution = SolutionAllBagTrain()
        let result = solution.bagMaxValue(capacity: size, weight: weight, value: value)
        print(result)
    }
}
